/*
 * @lc app=leetcode.cn id=542 lang=golang
 *
 * [542] 01 矩阵
 */

// @lc code=start

func updateMatrix(mat [][]int) [][]int {
	m, n := len(mat), len(mat[0])
	res := make([][]int, m)

	for i, _ := range res {
		res[i] = make([]int, n)
		for j, _ := range res[i] {
			res[i][j] = 100000
		}
	}
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if mat[i][j] == 0 {
				res[i][j] = 0

			} else {
				if i > 0 {
					res[i][j] = min(res[i][j], res[i-1][j]+1)
				}
				if j > 0 {
					res[i][j] = min(res[i][j], res[i][j-1]+1)
				}
			}

		}
	}

	for i := m - 1; i >= 0; i-- {
		for j := n - 1; j >= 0; j-- {
			if res[i][j] != 0 {
				if i < m-1 {
					res[i][j] = min(res[i][j], res[i+1][j]+1)
				}
				if j < n-1 {
					res[i][j] = min(res[i][j], res[i][j+1]+1)
				}
			}

		}
	}
	return res
}

func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}

// @lc code=end
